package pro.softzhang.algo.lc300;

import pro.softzhang.algo.common.Utils;
import pro.softzhang.algo.flag.knowledge.KBitManipulation;
import pro.softzhang.algo.flag.x.XOptimal;

/**
 * TODO
 */
@KBitManipulation
public class LC338_CountingBits {
    public static void main(String[] args) {
        int n = 6;
        Utils.printArr(new Solution().countBits(n));
    }

    @XOptimal
    static
    class Solution {
        public int[] countBits(int n) {
            int[] counter = new int[n + 1];
            for (int i = 1; i <= n; i++) {
                counter[i] = counter[i & (i - 1)] + 1;
            }
            return counter;
        }
    }

    static
    class Solution1 {
        public int[] countBits(int n) {
            int[] counter = new int[n + 1];
            for (int i = 0; i <= n; i++) {
                int tmp = i;
                while (tmp != 0) {
                    tmp = tmp & (tmp - 1);
                    counter[i]++;
                }
            }
            return counter;
        }
    }

    static
    class Solution2 {
        public int[] countBits(int n) {
            int[] counter = new int[n + 1];
            for(int i = 1; i <= n; i++) {
                counter[i] = counter[i >> 1] + (i & 1);
            }
            return counter;
        }
    }

    /**
     * 通过奇偶规律推出。
     */
    static
    class Solution3 {
        public int[] countBits(int n) {
            int[] dp = new int[n + 1];
            for (int i = 0; i <= n; i++) {
                if (i % 2 == 0) dp[i] = dp[i / 2];
                else dp[i] = dp[i / 2] + 1;
            }
            return dp;
        }
    }
}
